1. Field of the Invention
This invention relates to the field of computer graphics. More particularly, the present invention relates to the field of texture mapping by approximation.
2. Description of the Related Art
The above mentioned pending application includes a general background discussion on computer graphics and texture mapping. As such, this background section will focus on conventional texture mapping with perspective correction, methods for implementing the same, and their disadvantages.
Most conventional computer graphics systems include a display device for displaying a two dimensional image represented as a bit mapped array of evenly spaced pixels. Each pixel has a pixel value and is uniquely identified by an X-axis and a Y-axis coordinate value pair. This Cartesian X-Y coordinate representation is compatible with the majority of graphics display devices whose images are composed of a plurality of scan lines along the X-axis, e.g., cathode ray tubes (CRTs) and active/passive liquid crystal displays (LCDs).
Conventionally, texture is defined as a modulation of color, intensity, surface normal, transparency or other surface property applied to a surface of a graphics object in such a way that the pattern appears attached to the surface as the viewpoint and perspective varies. In order to realistically display three dimensional objects in a high quality two dimensional image on the display device, a perspectively correct texture mapping value, called a texel value, is generated for each pixel to modify the pixel values of the image.
Mathematical models have been employed to provide excellent image quality but they tend to be computationally intensive and very demanding of the processor on the computer graphics system. Typically, the generation of texel values include two divisional computations or their equivalent for each pixel of the image for computing the perspective correction. As is well known in the computer arts, divisional computations typically take a fairly large number of clock cycles, even when the processor is equipped with hardware dedicated to performing divisional computations. With powerful processors, such as a SPARC based processor, computing two divisions per pixel in real-time is possible but the resulting texture computations will limit the processor's ability to simultaneously support other processes. In the less powerful processors, such as Intel's 80486 SX microprocessor, real-time texture value computations requiring the two divisions per pixel can overwhelm the processor. Hence it is highly desirable to lower the computational requirements for generating a high quality perspectively corrected texture map. Typical conventional approaches reduce the total number of division computations by substituting linear interpolation for pixels at predetermined intervals between accurately computed division points.
As shown in FIGS. 1A and 1B, in a first pre-deterministic interpolation method, parent polygon 100 is progressively subdivided in a geometrical manner into a predetermined number of smaller child polygons 110, 120, 130, 140 . . . 190. Referring to FIG. 1C which shows one resulting child polygon 110 in greater detail, accurate texel values are computed for pairs of end points, e.g., end points 111a and 111z, where a scan line 111 intersects the boundaries of child polygon 110. Next, approximate texel values are computed for pixels 111b, 111c . . . 111y located between end points 111a, 111z, by linearly interpolating along scan line 111. This process is repeated for the remaining scan lines 112, 113, . . . 119 of child polygon 110, and also repeated in a similar manner for every scan line of the remaining child polygons 120, 130, . . . 190, until texel values for every pixel within parent polygon 100 have been computed.
Referring now to FIG. 2A, a second pre-deterministic interpolation method involves subdividing each scan line, e.g., scan line 210 of a polygon 200, into scan line segments delineated by a predetermined number of divisional points 212, 213, . . . 218, and end points 211, 219 as shown. For each scan line, e.g., scan line 210, accurate texel values are computed for end points 211, 219 and divisional points 212, 213, . . . 218. Next, as shown in FIG. 2B, texel values for the remaining pixels, 211a, 211b, . . . 211z, 212a, 212b . . . 212z, . . . , 218a, 218b, . . . 218z along scan line 210 are then computed by linear interpolation. This process is repeated for the remaining scan lines 220, 230, . . . 290, until texel values have been computed for every pixel in polygon 200.
In the above described conventional methods, linear interpolation of intermediate texel values can be accomplished with the following exemplary equations as applied to a polygon 2000 of FIG. 2C. Polygon 2000 is a triangle specified by a triple (x.sub.i, y.sub.i, z.sub.i, w.sub.i, u.sub.i, v.sub.i,), i=1,2,3, where (x.sub.i, y.sub.i) are the device coordinate of the triangle vertices, z.sub.i are the Z depth at the vertices, w.sub.i are the absolute value of the reciprocals of the w components of the vertices in the homogeneous clip coordinate system, and (u.sub.i, v.sub.i,) are the two-dimensional texture coordinates of the vertices. U, V, and W are the respective linearly interpolated values of u, v, w, along the left edge of triangle 2000 between (x.sub.1,y.sub.1,z.sub.1,w.sub.1,u.sub.1,v.sub.1) and (x.sub.3,y.sub.3,z.sub.3, w.sub.3,u.sub.3, v.sub.3). ##EQU1##
While the above described conventional methods do reduce the computational load on the processor by replacing some computationally intensive divisions with simpler linear interpolations, both conventional methods are disadvantageously inflexible, inefficient and/or produce unsatisfactory texel values. This is because pre-determining the amount of divisions works well only if texture variations between objects and texture gradients within objects over the entire image are both fairly constant. In practice, different objects in different images can have different texture properties and so no one predetermined level of scan line division will be optimal for all objects. For example, if the predetermined scan line segments are too short, i.e., the divisional points too closely spaced, an excessive amount of divisional computations will be required of the processor. Conversely, if the predetermined scan line segments are too large, grossly inaccurate approximations of texel values will result at distant pixel locations relative to the divisional points, and the overall texture quality of the image will be poor.